﻿namespace AdvancedTraining.Lesson48;

/// <summary>
/// 连接词查找算法 - LeetCode 472
/// 使用前缀树和动态规划优化来查找所有可以由其他至少两个不同单词组成的单词
/// </summary>
public class ConcatenatedWords
{
    /// <summary>
    /// 提前准备好动态规划表
    /// </summary>
    private static readonly int[] Dp = new int[1000];

    /// <summary>
    /// 将字符串插入到前缀树中
    /// </summary>
    /// <param name="root">前缀树根节点</param>
    /// <param name="s">要插入的字符数组</param>
    /// <exception cref="ArgumentNullException">当根节点为null时抛出异常</exception>
    private static void Insert(TrieNode root, char[] s)
    {
        if (root == null) throw new ArgumentNullException(nameof(root));
        foreach (var c in s)
        {
            var path = c - 'a';
            if (root.NextList[path] == null) root.NextList[path] = new TrieNode();
            root = root.NextList[path];
        }

        root.End = true;
    }

    /// <summary>
    /// 方法1：前缀树优化查找所有连接词
    /// 时间复杂度：O(N * L^2)，其中N是单词数量，L是平均单词长度
    /// 空间复杂度：O(N * L)，用于存储前缀树
    /// </summary>
    /// <param name="words">单词数组</param>
    /// <returns>所有连接词的列表</returns>
    public static IList<string> FindAllConcatenatedWordsInADict1(string[]? words)
    {
        IList<string> ans = new List<string>();
        if (words == null || words.Length < 3) return ans;
        // 字符串数量 >= 3个
        Array.Sort(words, (str1, str2) => str1.Length - str2.Length);
        var root = new TrieNode();
        foreach (var str in words)
        {
            var s = str.ToCharArray(); // "" 题目要求
            if (s.Length > 0 && Split1(s, root, 0))
                ans.Add(str);
            else
                Insert(root, s);
        }

        return ans;
    }

    /// <summary>
    /// 字符串s[i....]能不能被分解？
    /// 之前的元件，全在前缀树上，r就是前缀树头节点
    /// </summary>
    /// <param name="s">字符数组</param>
    /// <param name="r">前缀树根节点</param>
    /// <param name="i">当前开始位置</param>
    /// <returns>是否可以被分解</returns>
    private static bool Split1(char[] s, TrieNode r, int i)
    {
        var ans = false;
        if (i == s.Length)
        {
            // 没字符了！
            ans = true;
        }
        else
        {
            // 还有字符
            var c = r;
            // s[i.....]
            // s[i..end]作前缀，看看是不是一个元件！f(end+1)...
            for (var end = i; end < s.Length; end++)
            {
                var path = s[end] - 'a';
                if (c.NextList[path] == null) break;
                c = c.NextList[path];
                if (c.End && Split1(s, r, end + 1))
                {
                    ans = true;
                    break;
                }
            }
        }

        return ans;
    }

    /// <summary>
    /// 方法二：前缀树优化 + 动态规划优化查找所有连接词
    /// 时间复杂度：O(N * L^2)，其中N是单词数量，L是平均单词长度
    /// 空间复杂度：O(N * L + L)，用于存储前缀树和动态规划表
    /// </summary>
    /// <param name="words">单词数组</param>
    /// <returns>所有连接词的列表</returns>
    public static IList<string> FindAllConcatenatedWordsInADict2(string[]? words)
    {
        IList<string> ans = new List<string>();
        if (words == null || words.Length < 3) return ans;
        Array.Sort(words, (str1, str2) => str1.Length - str2.Length);
        var root = new TrieNode();
        foreach (var str in words)
        {
            var s = str.ToCharArray();
            // 根据Java版本，使用相同的DP初始化方式
            for (int j = 0; j <= s.Length; j++)
            {
                Dp[j] = 0;
            }
            if (s.Length > 0 && Split2(s, root, 0, Dp))
                ans.Add(str);
            else
                Insert(root, s);
        }

        return ans;
    }

    /// <summary>
    /// 使用动态规划优化的字符串分割方法
    /// </summary>
    /// <param name="s">字符数组</param>
    /// <param name="r">前缀树根节点</param>
    /// <param name="i">当前开始位置</param>
    /// <param name="dp">动态规划表</param>
    /// <returns>是否可以被分解</returns>
    private static bool Split2(char[] s, TrieNode r, int i, int[] dp)
    {
        if (dp[i] != 0) return dp[i] == 1;
        var ans = false;
        if (i == s.Length)
        {
            ans = true;
        }
        else
        {
            var c = r;
            for (var end = i; end < s.Length; end++)
            {
                var path = s[end] - 'a';
                if (c.NextList[path] == null) break;
                c = c.NextList[path];
                if (c.End && Split2(s, r, end + 1, dp))
                {
                    ans = true;
                    break;
                }
            }
        }

        dp[i] = ans ? 1 : -1;
        return ans;
    }

    /// <summary>
    /// 前缀树节点类
    /// </summary>
    public class TrieNode
    {
        /// <summary>
        /// 26个字母的子节点指针
        /// </summary>
        public readonly TrieNode?[] NextList = new TrieNode[26];

        /// <summary>
        /// 标记是否为单词结尾
        /// </summary>
        public bool End;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 连接词查找算法测试 ===");

        // 测试用例1：LeetCode官方示例
        var test1 = new[] { "cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat" };
        var result1 = FindAllConcatenatedWordsInADict1(test1);
        var result2 = FindAllConcatenatedWordsInADict2(test1);

        Console.WriteLine("测试用例1: [" + string.Join(", ", test1.Select(w => $"\"{w}\"")) + "]");
        Console.WriteLine($"方法1结果: [{string.Join(", ", result1.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"方法2结果: [{string.Join(", ", result2.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"预期结果: [\"catsdogcats\", \"dogcatsdog\", \"ratcatdogcat\"]");
        Console.WriteLine($"方法1匹配: {result1.Count == 3 && result1.Contains("catsdogcats") && result1.Contains("dogcatsdog") && result1.Contains("ratcatdogcat")}");
        Console.WriteLine($"方法2匹配: {result2.Count == 3 && result2.Contains("catsdogcats") && result2.Contains("dogcatsdog") && result2.Contains("ratcatdogcat")}");
        Console.WriteLine();

        // 测试用例2：简单情况
        var test2 = new[] { "a", "b", "ab", "abc" };
        var result3 = FindAllConcatenatedWordsInADict1(test2);
        var result4 = FindAllConcatenatedWordsInADict2(test2);

        Console.WriteLine("测试用例2: [" + string.Join(", ", test2.Select(w => $"\"{w}\"")) + "]");
        Console.WriteLine($"方法1结果: [{string.Join(", ", result3.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"方法2结果: [{string.Join(", ", result4.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"预期结果: [\"ab\"]");
        Console.WriteLine();

        // 测试用例3：没有连接词
        var test3 = new[] { "apple", "orange", "banana" };
        var result5 = FindAllConcatenatedWordsInADict1(test3);
        var result6 = FindAllConcatenatedWordsInADict2(test3);

        Console.WriteLine("测试用例3: [" + string.Join(", ", test3.Select(w => $"\"{w}\"")) + "]");
        Console.WriteLine($"方法1结果: [{string.Join(", ", result5.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"方法2结果: [{string.Join(", ", result6.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"预期结果: []");
        Console.WriteLine();

        // 测试用例4：复杂连接词
        var test4 = new[] { "cat", "dog", "catdog", "dogcat", "catdogcat" };
        var result7 = FindAllConcatenatedWordsInADict1(test4);
        var result8 = FindAllConcatenatedWordsInADict2(test4);

        Console.WriteLine("测试用例4: [" + string.Join(", ", test4.Select(w => $"\"{w}\"")) + "]");
        Console.WriteLine($"方法1结果: [{string.Join(", ", result7.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"方法2结果: [{string.Join(", ", result8.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"预期结果: [\"catdog\", \"dogcat\", \"catdogcat\"]");
        Console.WriteLine();

        // 测试用例5：空数组
        var test5 = new string[0];
        var result9 = FindAllConcatenatedWordsInADict1(test5);
        var result10 = FindAllConcatenatedWordsInADict2(test5);

        Console.WriteLine("测试用例5: []");
        Console.WriteLine($"方法1结果: [{string.Join(", ", result9.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"方法2结果: [{string.Join(", ", result10.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"预期结果: []");
        Console.WriteLine();

        // 测试用例6：包含空字符串
        var test6 = new[] { "", "a", "b", "ab" };
        var result11 = FindAllConcatenatedWordsInADict1(test6);
        var result12 = FindAllConcatenatedWordsInADict2(test6);

        Console.WriteLine("测试用例6: [\"\", \"a\", \"b\", \"ab\"]");
        Console.WriteLine($"方法1结果: [{string.Join(", ", result11.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"方法2结果: [{string.Join(", ", result12.Select(w => $"\"{w}\""))}]");
        Console.WriteLine($"预期结果: [\"ab\"] (空字符串被忽略)");
        Console.WriteLine();

        Console.WriteLine("=== 测试完成 ===");
    }
}